public class Sort {
    /**
     * 直接插入排序
     * 时间复杂度:O(n^2)
     * 空间复杂度:O(1)
     * 稳定性:稳定
     */

    public void InsertSort(int[] array){
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i-1;
            for (; j >=0 ;j--) {
                if(array[j]>tmp){
                    array[j+1] = array[j];
                }else {
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }

    /**
     *希尔排序
     * 时间复杂度:O(n^1.3~n^1.5)
     * 空间复杂度:O(1)
     * 稳定性:不稳定
     */

    public void shell(int[] array,int gap){
        for (int i = gap; i < array.length ; i++) {
            int j = i-gap;
            int tmp = array[i];
            for (; j >=0; j-=gap) {
                if (array[j] > array[j+gap]) {
                    array[j+gap] = array[j];
                }else{
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }
    public void shellSort(int[] array){
        int gap = array.length;;
        while(gap>1){
            shell(array,gap);
            gap/=2;
        }
        shell(array,1);
    }

    /**
     * 选择排序
     * 时间复杂度:O(n^2)
     * 空间复杂度:O(1)
     * 稳定性:不稳定
     */

    public void selectSort(int[] array){
        int minIndex = 0;
        for (int i = 0; i < array.length ; i++) {
            minIndex = i;
            for (int j = i+1; j < array.length ; j++) {
                if(array[j]<array[minIndex]){
                    minIndex = j;
                }
            }
            swap(array,minIndex,i);
        }
    }
    public void swap(int[] array,int i,int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    /**
     * 堆排序
     * 时间复杂度:O(n*logn)
     * 空间复杂度:O(1)
     * 稳定性:不稳定
     * @param array
     */

    public void heapSort(int[] array){
        creatBigheap(array);
        int end = array.length-1;
        while(end>=0){
            swap(array,end,0);
            shitfdown(array,0,end);
            end--;
        }
    }
    public void creatBigheap(int[] array){
        for (int parent = (array.length-1-1)/2; parent >=0 ; parent--) {
            shitfdown(array,parent, array.length);
        }
    }
    public void shitfdown(int[] array,int parent,int len){
        int child = 2*parent+1;
        while(child<len){
            if(child+1<len&&array[child]<array[child+1]){
                child++;
            }
            if(array[child]>array[parent]){
                swap(array,child,parent);
                parent = child;
                child = 2*parent+1;
            }else{
                break;
            }
        }
    }
    /**
     * 交换排序：冒泡排序
     */

    public void bubbleSort(int[] array){
        for (int i = 0; i < array.length-1; i++) {
            boolean flg = false;
            for (int j = 0; j <array.length-1-i ; j++) {
                if(array[j+1]<array[j]){
                    swap(array,j+1,j);
                    flg = true;
                }
            }
            if(flg==false){
                break;
            }
        }
    }

    /**
     * 交换排序：快速排序
     */

    public void quickSort(int[] array){
        quick(array,0, array.length-1);
    }
    public void quick(int[] array,int left,int right){
        if(left>=right){
            return;
        }
        int index = minNumIndex(array,left,right);
        swap(array,index,left);
        int poive = partition(array,left,right);
        quick(array,left,poive-1);
        quick(array,poive+1,right);
    }
    public int partitionHoare(int[] array,int start,int end){
        int i = start;
        int key = array[start];
        while(start<end){
            while(start<end&&array[end]>=key){
                end--;
            }
            while(start<end&&array[start]<=key){
                start++;
            }
            swap(array,start,end);
        }
        swap(array,i,start);
        return start;
    }
    public int partition2(int[] array,int start,int end){
        int key = array[start];
        while(start<end){
            while (start<end&&array[end]>=key){
                end--;
            }
            array[start] = array[end];
            while(start<end&&array[start]<=key){
                start++;
            }
            array[end] = array[start];
        }
        array[start] = key;
        return start;
    }
    public int partition(int[] array,int start,int end){
        int prev = start;
        int cur = start+1;
        while(cur<=end){
            if(array[cur]<array[start]&&array[++prev]!=array[cur]){
                swap(array,cur,prev);
            }
            cur++;
        }
        swap(array,prev,start);
        return prev;
    }
    public int minNumIndex(int[] array,int left,int right){
        int mid = (right+left)/2;
        if(array[left]>array[right]){
            if(array[mid]>array[left]){
                return left;
            }else if(array[mid]<array[right]){
                return right;
            }else {
                return mid;
            }
        }else{
            if(array[mid]>array[right]){
                return right;
            }else if(array[mid]<array[left]){
                return left;
            }else{
                return mid;
            }
        }
    }

}
